Let $G$ be a simple, undirected graph. In this paper, we initiate the study of independent Roman $\{3\}$-domination. A function $g : V(G) \rightarrow \lbrace 0, 1, 2, 3 \rbrace$ having the property that $\sum_{v \in N_G(u)}^{} g(v) \geq 3$, if $g(u) = 0$, and $\sum_{v \in N_G(u)}^{} g(v) \geq 2$, if $g(u) = 1$ for any vertex $u \in V(G)$, where $N_G(u)$ is the set of vertices adjacent to $u$ in $G$, and no two vertices assigned positive values are adjacent is called an \textit{ independent Roman $\{3\}$-dominating function} (IR3DF) of $G$. The weight of an IR3DF $g$ is the sum $g(V) = \sum_{v \in V}g(v)$. Given a graph $G$ and a positive integer $k$, the independent Roman $\{3\}$-domination problem (IR3DP) is to check whether $G$ has an IR3DF of weight at most $k$. We investigate the complexity of IR3DP in bipartite and chordal graphs. The minimum independent Roman $\lbrace 3 \rbrace$-domination problem (MIR3DP) is to find an IR3DF of minimum weight in the input graph. We show that MIR3DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs. We also show that the domination problem and IR3DP are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MIR3DP.

Let G be a graph with vertex set V (G). A Roman dominating function (RDF) on a graph G is a function f: V (G) →, {0, 1,2} such that every vertex v with f(v) = 0 is adjacent to a vertex u with f(u) = 2. If f is an RDF on G, then let Vi = {v ,V (G): f(v) = i} for i ,{0,1,2}. An RDF f is called a restrained (total) Roman dominating function if the subgraph induced by V0 (induced by V1 , V2) has no isolated vertex. A total and restrained Roman dominating function is a total restrained Roman dominating function. The total restrained Roman domination number ɤ, trR(G) on a graph G is the minimum weight of a total restrained Roman dominating function on the graph G. We initiate the study of total restrained Roman domination number and present several sharp bounds on ɤ, trR(G). In addition, we determine this parameter for some classes of graphs.

‎‎A Roman dominating function (RDF) on a graph is a function satisfying the condition that every vertex with is adjacent to at least one vertex for which . The weight of an RDF is the sum of the weights of the vertices under . The Roman domination number, of is the minimum weight of an RDF in . The Roman domination polynomial of a graph of order is the polynomial , where is the number of RDFs of with weight . In this paper we prove properties of Roman domination polynomials and determine in several classes of graphs by new approaches. We also present bounds on the number of all Roman domination polynomials in a graph.

Let S = (G,σ, ) be a signed graph. A function f: V →, {0, 1, 2} is a Roman dominating function on S if (i) for each v ϵ,V,f(N[v]) = f(v)+ ∑,u ϵ,N(v) σ, (uv) f(u)≥,1 and (ii) for each vertex v with f(v) = 0, there exists a vertex u ϵ,N +(v) such that f(u) = 2: In this paper we initiate a study on Roman dominating function on signed graphs. We characterise the signed paths, cycles and stars that admit a Roman dominating function.

Let $G=(V,E)$\ be a simple graph and $f:V\rightarrow\{0,1,2,3\}$ be a function. A vertex $u$ with $f\left( u\right) =0$ is called an undefended vertex with respect to $f$ if it is not adjacent to a vertex $v$ with $f(v)\geq2.$ We call the function $f$ a generous Roman dominating function (GRDF) if for every vertex with $f\left( u\right) =0$ there exists at least a vertex $v$ with $f(v)\geq2$ adjacent to $u$ such that the function $f^{\prime}:V\rightarrow \{0,1,2,3\}$, defined by $f^{\prime}(u)=\alpha$, $f^{\prime}(v)=f(v)-\alpha$ where $\alpha=1$ or $2$, and $f^{\prime}(w)=f(w)$ if $w\in V-\{u,v\}$ has no undefended vertex. The weight of a generous Roman dominating function $f$ is the value $f(V)=\sum_{u\in V}f(u)$. The minimum weight of a generous Roman dominating function on a graph $G$\ is called the generous Roman domination number of $G$, denoted by $\gamma_{gR}\left( G\right) $. In this paper, we initiate the study of generous Roman domination and show its relationships. Also, we give the exact values for paths and cycles. Moreover, we present an upper bound on the generous Roman domination number, and we characterize cubic graphs $G$ of order $n$ with $\gamma_{gR}\left( G\right) =n-1$, and a Nordhaus-Gaddum type inequality for the parameter is also given. Finally, we study the complexity of this parameter.

Let G=(V, E) be a graph and let f: V(G)→ {0, 1, 2} be a function. A vertex v is protected with respect to f, if f(v)>0 or f(v)=0 and v is adjacent to a vertex of positive weight. The function f is a co-Roman dominating function, abbreviated CRDF if: (i) every vertex in V is protected, and (ii) each u∈ V with positive weight has a neighbor v∈ V with f(v)=0 such that the function f_uv: V→ {0, 1, 2}, defined by f_uv (v)=1, f_uv (u)=f(u)-1 and f_uv (x)=f(x)for x∈ V-\{v, u}, has no unprotected vertex. The weight of f is ω (f)=∑ _(v∈ V)▒ 〖 f(v)〗 . The co-Roman domination number of a graph G, denoted by γ _cr G), is the minimum weight of a co-Roman dominating function on G. In this paper, we first present an upper bound on the co-Roman domination number of trees in terms of order, the number of leaves and supports. Then we find bounds on the co-Roman domination number of a graph and its other dominating parameters.

A total Roman dominating function on a graph G is a function f: V (G)! f0; 1; 2g such that for every vertex v 2 V (G) with f(v) = 0 there exists a vertex u 2 V (G) adjacent to v with f(u) = 2, and the subgraph induced by the set fx 2 V (G): f(x)  1g has no isolated vertices. The total Roman domination number of G, denoted tR(G), is the minimum weight! (f) = P v2V (G) f(v) among all total Roman dominating functions f on G. It is known that tR(G)  t2(G) + (G) for any graph G with neither isolated vertex nor components isomorphic to K2, where t2(G) and (G) represent the semitotal domination number and the classical domination number, respectively. In this paper we give a constructive characterization of the trees that satisfy the equality above.

Let G = (V, E) be a simple, undirected and connected graph. A Roman dominating function (RDF) on the graph G is a function f: V → {0, 1, 2} such that each vertex v ∈ V with f(v) = 0 is adjacent to at least one vertex u ∈ V with f(u) = 2. A total Roman dominating function (TRDF) of G is a function f: V → {0, 1, 2} such that (i) it is a Roman dominating function, and (ii) the vertices with non-zero weights induce a subgraph with no isolated vertex. The total Roman dominating set (TRDS) problem is to minimize the associated weight, f(V ) = P u∈V f(u), called the total Roman domination number (γtR(G)). Similarly, a subset S ⊆ V is said to be a total dominating set (TDS) on the graph G if (i) S is a dominating set of G, and (ii) the induced subgraph G[S] does not have any isolated vertex. The objective of the TDS problem is to minimize the cardinality of the TDS of a given graph. The TDS problem is NP-complete for general graphs. In this paper, we propose a simple 10. 5-factor approximation algorithm for TRDS problem in UDGs. The running time of the proposed algorithm is O(|V | log k), where k is the number of vertices with weights 2. It is an improvement over the best-known 12-factor approximation algorithm with running time O(|V | log k) available in the literature. Next, we propose another algorithm for the TDS problem in UDGs, which improves the previously best-known approximation factor from 8 to 7. 79. The running time of the proposed algorithm is O(|V | + |E|).

Let $G=(V,E)$ be a simple graph and $f$ a function defined from $V$ to $\{0,1,2,3\}.$ A vertex $u$ with $f(u)=0$ is called an undefended vertex with respect to $f$ if it is not adjacent to a vertex $v$ with $f(v)\geq2$. The function $f$ is called a generous Roman dominating function (GRD-function) if for every vertex with $f(u)=0$ there exists at least a vertex $v$ with $f(v)\geq2$ adjacent to $u$ such that the function $f^{\prime}:V\rightarrow\{0,1,2,3\}$, defined by $f^{\prime}(u)=\alpha$, $f^{\prime}(v)=f(v)-\alpha$ where $\alpha\in\{1,2\}$, and $f^{\prime}(w)=f(w)$ if $w\in V-\{u,v\}$ has no undefended vertex. The weight of a GRD-function $f$ is the sum of its function values over all vertices, and the minimum weight of a GRD-function on $G$ is the generous Roman domination number $\gamma_{gR}(G)$. The $\gamma_{gR}$-stability $\mathrm{st}_{\gamma_{gR}}(G)$ (resp. $\gamma_{gR}^{-}$-stability $\mathrm{st}_{\gamma_{gR}}^{-}(G)$, $\gamma_{gR}^{+}$-stability $\mathrm{st}_{\gamma_{gR}}^{+}(G)$) of $G$ is defined as the order of the smallest set of vertices whose removal changes (resp. decreases, increases) the generous Roman domination number. In this paper, we first determine the exact values of $\gamma_{gR}$-stability for some special classes of graphs, and then we present some bounds on $\mathrm{st}_{\gamma_{gR}}(G)$. We also characterize graphs with large $\mathrm{st}_{\gamma_{gR}}(G)$.Moreover, we show that if $T$ is a nontrivial tree, then $\mathrm{st}_{\gamma_{gR}}(T)\leq2,$ and if further $T$ has maximum degree $\Delta\geq3$, then $\mathrm{st}_{\gamma_{gR}}^{-}(T)\leq\Delta-1$.